package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 496.下一个最大元素Ⅰ
 * 如果不存在下一个更大元素，那么本次查询的答案是 -1
 * nums1和nums2中所有整数互不相同
 * nums1 中的所有整数同样出现在 nums2 中
 *
 * 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
 * 输出：[-1,3,-1]
 */
public class Num_496 {

    //单调栈: 从栈顶到栈底，元素要么单调递增排列，要么单调递减排列
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        //存放nums2中每个元素的下一个最大元素
        Map<Integer,Integer> map = new HashMap<>();
        //用单调栈找最大元素
        Stack<Integer> stack = new Stack<>();
        //因为是向后找，所以就倒着遍历nums2
        for(int i = nums2.length - 1; i >= 0; i--) {
            //栈不为空且栈顶元素 <= 当前元素，把这种元素全部出栈
            while(!stack.isEmpty() && stack.peek() <= nums2[i]) {
                stack.pop();
            }
            //此时需要判断栈是否为空
            map.put(nums2[i], stack.isEmpty() ? -1:stack.peek());
            //把当前的元素作为大元素添到栈中
            stack.push(nums2[i]);
        }

        //存放结果，长度和nums1一样
        int[] ret = new int[nums1.length];
        for(int i=0; i< nums1.length; i++){
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}
